"""
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
1:1                                            1=1           1+0个2
2:11; 2                                        1+1=1+1       1+1个2
3:111; 21;12;                                  1+2=1+2       1+1个2余1
4:1111; 211;121,112; 22                        1+3+1=1+3+1   1+1个2余2+2个2余0
5:11111; 2111,1211,1121,1112;221,212,122       1+4+3=1+4+3   1+1个2余3+2个3余1
6:111111; 21111,12111,11211,11121,11112;2211,2121,2112,1221,1212,1122,222   1+4+3=1+5+6+1   1+1个2余3+2个3余1
"""


class Solution:
    # def climbStairs(self, n: int) -> int:
    def climbStairs(self, n):
        count = 0
        if n == 1:
            count = 1
        elif n == 2:
            count = 2
        else:
            n1 = 1
            n2 = 2
            for _ in range(n - 2):
                n1, n2 = n2, n1 + n2
            count = n2
        return count

    def climbStairs2(self, n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        else:
            return self.climbStairs2(n - 1) + self.climbStairs2(n - 2)

    def climbStairs1(self, n):
        count = 1  # 0个2
        for i in range(1, n + 1):
            if 2 * i > n:
                break
            # 从n-2*i+i数里取i个排列
            count += self.arrang(n - 2 * i + i, i)
        return count

    def arrang(self, n, m):  # m <= n
        # 从n个元素中，选取m个数字的排列
        if m == n:
            return 1
        else:
            n * self.arrang(n - 1, m)
        return n


# print(Solution().climbStairs(1)) #1
# print(Solution().climbStairs(2)) #2
# print(Solution().climbStairs(3)) #3
# print(Solution().climbStairs(4)) #5
# print(Solution().climbStairs(5)) #8
# print(Solution().climbStairs(6)) #13
